package main

import (
	"fmt"
	"sort"
)

// 看了一个人的思路
// 找到nums[i] 比nums[i+1]小的时候，
// 就将nums[i]跟nums[i+1]到nums[nums.length - 1]当中找到
// 一个最小的比nums[i]大的元素交换。交换后，再把nums[i+1]到nums[nums.length-1]排序

func nextPermutation(nums []int) {
	// nums[0] = 1
	fmt.Println(nums)
	length := len(nums)
	index := -1
	for i := 1; i < length; i++ {
		if nums[length-i-1] < nums[length-i] {
			// fmt.Println(nums[length-i-1])
			index = length - i - 1
			break
		}
	}
	fmt.Println(index)
	if index == -1 {
		sort.Ints(nums)
		return
	}
	fmt.Println(nums)
	// 将nums[i]　跟nums[i+1]到nums[nums.length - 1]当中找到
	// 一个最小的比nums[i]大的元素交换
	tmp := index + 1
	for i := index; i < length; i++ {
		fmt.Println("i=", i, nums[index], nums[i], tmp)
		if nums[i] < nums[tmp] && nums[index] < nums[i] {
			tmp = i
		}
	}
	// 交换找到的元素
	nums[index], nums[tmp] = nums[tmp], nums[index]

	fmt.Println("tmp=", tmp)
	right := nums[index+1:]
	sort.Ints(right)
	fmt.Println("right=", right)
	fmt.Println(nums)
}

func main() {
	// nums := []int{1, 2, 3, 4}
	// nums := []int{3, 4, 2, 1}
	nums := []int{1, 3, 2}
	nextPermutation(nums)
}
